Motivation

Diffie-Hellman Key Exchange is not used anymore due to the Index Calculus attack. Elliptic Curve Diffie-Hellman is now the de facto standard, but RSA is still used in many legacy situations.

In finite field cryptography, you want your chosen group to have a large prime order so that Pohlig-Hellman doesn’t work and you want the group operation to be easy so that encryption and decryption can be done efficiently.

Elliptic curve groups satisfy these properties.

Unit Circle Group

The unit circle group can be used as an example, but is not secure as the Discrete Logarithm Problem is easily solved: %%🖋 Edit in Excalidraw%%

Edwards Curve Group

%%🖋 Edit in Excalidraw%% Weierstrass equation $y^2 = x^3 +Ax + B$ is one of the ways of representing elliptic curves over $F_p$.

History

First curve (P-256) was standardised in 2004 by NIST, and was discovered in 2013 that the NSA had a backdoor in it, which happens pretty much every time there’s a NIST standards competition.

In 2005, Curve25519 was proposed, and was standardised in 2016 by the IETF along with Curve 448. It was also standardised by NIST in 2017.

Elliptic Curve Signatures (ECDSA)

[[ElGamal]] works with elliptic curves:

%%🖋 Edit in Excalidraw%%

Pairings

Pairings are bi-linear maps of groups: %%🖋 Edit in Excalidraw%% The only well studied pairing has $G_1$ and $G_2$ be elliptic curve groups, and $G_3$ be a finite field group.

Pairings in (simplified) IBE (Boneh-Franklin)

Scenario: Bob authenticates an anonymous Alice. %%🖋 Edit in Excalidraw%%

Unique applications of ECC

• Identity-based encryption (proof of participation without revealing identity)
• Attribute-based encryption (proof of some attribute over group without revealing identity)
• Other privacy-enhancing techniques
• Tripartite key exchange with only one round of communication

Related Reading

• Elliptic Curves